package com.lw.leetcode.back.c;

import com.lw.test.util.Utils;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created with IntelliJ IDEA.
 * back
 * 126. 单词接龙 II
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/20 11:23
 */
public class LadderLength126 {


    public static void main(String[] args) {
        LadderLength126 test = new LadderLength126();

        // "hit" -> "hot" -> "dot" -> "dog" -> "cog"
        // "hit" -> "hot" -> "lot" -> "log" -> "cog"
//        String beginWord = "hit";
//        String endWord = "cog";
//        List<String> wordList = Arrays.asList("hot","dot","dog","lot","log","cog");

        // 输出：{}
//        String beginWord = "hit";
//        String endWord = "cog";
//        List<String> wordList = Arrays.asList("hot","dot","dog","lot","log");

        // 输出：{}
        String beginWord = "abc";
        String endWord = "def";
        String[] arr = Utils.getStrs(550, 3, 'a', 'n');
        arr[0] = endWord;
        List<String> wordList = Arrays.stream(arr).distinct().collect(Collectors.toList());

        System.out.println();
        System.out.println("\"" + beginWord + "\"");
        System.out.println("\"" + endWord + "\"");
        String s = "[\"" + wordList.stream().collect(Collectors.joining("\",\"")) + "\"]";
        System.out.println(s);
        System.out.println();
        System.out.println(wordList.size());
        List<List<String>> ladders = test.findLadders(beginWord, endWord, wordList);

        System.out.println(ladders);
    }

    private Map<String, List<String>> map = new HashMap<>();
    private List<String> wordList;

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        this.wordList = wordList;
        int size = wordList.size();
        char[][] arr = new char[size][];
        int[] flags = new int[size];
        int flag = -1;
        Map<String, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < size; i++) {
            String str = wordList.get(i);
            arr[i] = str.toCharArray();
            if (str.equals(beginWord)) {
                flag = i;
            }
            indexMap.put(str, i);
        }
        Arrays.fill(flags, 1024);
        if (flag == -1) {
            find(beginWord, beginWord.toCharArray(), arr, 0);
        } else {
            flags[flag] = 1;
        }
        for (int i = 0; i < size; i++) {
            find(wordList.get(i), arr[i], arr, i + 1);
        }
        Map<String, List<String>> path = new HashMap<>();
        LinkedList<String> list = new LinkedList<>();
        list.add(beginWord);
        List<List<String>> values = new ArrayList<>();
        int n = 0;
        while (!list.isEmpty()) {
            n++;
            if (!values.isEmpty()) {
                break;
            }
            int s = list.size();
            for (int i = 0; i < s; i++) {
                String v = list.pollFirst();
                if (endWord.equals(v)) {
                    List<String> t = new ArrayList<>();
                    addPath(path, v, t, values);
                    values.add(t);
                } else {
                    List<String> li = map.get(v);
                    if (li == null) {
                        continue;
                    }
                    for (String s1 : li) {
                        Integer index = indexMap.get(s1);
                        if (index == null || flags[index] < n) {
                            continue;
                        }
                        if (flags[index] != n) {
                            list.addLast(s1);
                        }
                        flags[index] = n;
                        path.computeIfAbsent(s1, g -> new ArrayList<>()).add(v);
                    }
                }
            }
        }
        for (List<String> value : values) {
            Collections.reverse(value);
        }
        return values;
    }

    private void addPath(Map<String, List<String>> path, String key, List<String> items, List<List<String>> values) {
        while (key != null) {
            items.add(key);
            List<String> list = path.get(key);
            if (list == null) {
                break;
            }
            key = list.get(0);
            if (list.size() > 1) {
                for (int i = 1; i < list.size(); i++) {
                    List<String> copy = new ArrayList<>(items);
                    values.add(copy);
                    addPath(path, list.get(i), copy, values);
                }
            }
        }
    }

    private void find(String item, char[] items, char[][] arr, int st) {
        for (int i = arr.length - 1; i >= st; i--) {
            char[] chars = arr[i];
            if (find(items, chars)) {
                map.computeIfAbsent(item, v -> new ArrayList<>()).add(wordList.get(i));
                map.computeIfAbsent(wordList.get(i), v -> new ArrayList<>()).add(item);
            }
        }
    }

    private boolean find(char[] as, char[] bs) {
        int length = as.length;
        int c = 0;
        for (int i = 0; i < length; i++) {
            if (as[i] != bs[i]) {
                c++;
            }
        }
        return c == 1;
    }

}
